This paper presents a new anytime incremental search algorithm, AD*-Cut. AD*-Cut is based on two algorithms, namely, Anytime Repairing A* (ARA*) and the novel incremental search algorithm, D* Extra Lite. D* Extra Lite reinitializes (cuts) entire search-tree branches that have been affected by changes in an environment, and D* Extra Lite appears to be quicker than the reinitialization during the search utilized by the popular incremental search algorithm, D* Lite. The search-tree branch cutting is a simple and robust technique that can be easily applied to ARA*. Consequently, AD*-Cut extends D* Extra Lite in the same manner, as the state-of-the-art Anytime D* (AD*) algorithm extends D* Lite. The benchmark results suggest that AD*-Cut is quicker and achieves shorter paths than AD* when used for path planning on 3D state-lattices (a 2D position with rotation).

Incremental search algorithms reuse information from previous searches to speed up the current search and are thus often able to find shortest paths for series of similar search problems faster than by solving each search problem independently from scratch. However, they do poorly on moving target search problems, where both the start and goal cells change over time. In this paper, we thus develop Fringe-Retrieving A* (FRA*), an incremental version of A* that repeatedly finds shortest paths for moving target search in known gridworlds. We demonstrate experimentally that it runs up to one order of magnitude faster than a variety of state-of-the-art incremental search algorithms applied to moving target search in known gridworlds.

Incremental search reuses information from previous searches to find solutions to a series of similar search problems potentially faster than is possible by solving each search problem from scratch. This is important because many AI systems have to adapt their plans continuously to changes in (their knowledge of) the world. In this article, we give an overview of incremental search, focusing on LIFELONG PLANNING A*, and outline some of its possible applications in AI.